package easy;

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1:
 *
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 *
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 说明:
 *
 * 所有输入只包含小写字母 a-z 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class DAY05 {
    public static void main(String[] args) {
        String[] strs = {"flower","flow","xxflight"};
        System.out.println("公共前缀 = " + test(strs));
    }

    public static String test(String[] strings) {
        String str = "";
        if (strings.length == 1) return strings[0];
        str = strings[0];
        for (int index = 1; index < strings.length; index++) {
            while (!strings[index].startsWith(str)) {
                if (str.length() > 1) {
                    str = str.substring(0, str.length() - 1);
                } else {
                    return "";
                }
            }
        }
        return str;
    }


    public static String longestCommonPrefix2(String[] strings) {
        if (strings.length == 0)    return "";
        if (strings.length == 1)    return strings[0];
        String preFix = strings[0];
        for (int index = 1; index < strings.length; index++) {
            while (strings[index].indexOf(preFix) != 0) {
                if (preFix.equals("")) return "";
                preFix = preFix.substring(0, preFix.length() - 1);
            }
        }
        return preFix;
    }


    /**
     * 思路:吧第一个元素当做是最长前缀,在其他元素中查找是否包含,不包含就裁剪掉最后一个字母,循环进行比较
     * 执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗 :38.3 MB, 在所有 Java 提交中击败了5.00%的用户
     * 主要考察内容:
     *      xx.indexof
     *      xx.substring
     */
    static public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)   return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                if (prefix.isEmpty()) {
                    return "";
                } else {
                    prefix = prefix.substring(0, prefix.length()-1);
                }
            }
        }
        return prefix;

    }
}
